#ifndef GRAPH
#define GRAPH

#include "List/linked_List.hpp"
#include "List/array_list.hpp"
#include <iostream>

// 基于邻接链表实现的有向图
// Vertex Attribute顶点属性， Edge Attribute边属性
template <typename Vattr, typename Eattr>
class Graph {
public:
    struct Vertex;
    struct Edge;

    Graph();
    size_t set(const Vattr &attr);
    void link(const size_t from, const size_t to, const Eattr &attr);
    const Vertex &get(const size_t id) const;
    void remove(const size_t id);
    void unlink(const size_t from, const size_t to);
    const ArrayList<Vertex> &vertexes() const;
    const ArrayList<std::reference_wrapper<Edge>> &edges() const;
    void clear();
    ~Graph();

    struct Vertex {
        size_t id;
        LinkedList<Edge> edges;
        Vattr attr;

        Vertex(const size_t id=0, const Vattr &attr=Vattr()): id(id), attr(attr) {}
        bool operator==(const Vertex &v) { return v.id == id; }

        struct hash {
            size_t operator()(const Vertex &v) const {
                return v.id;
            }
        };

        friend std::ostream &operator<<(std::ostream &os, const Vertex v) {
            os << v.attr;
            return os;
        }
    };

    struct Edge {
        size_t from;
        size_t to;
        Eattr attr;

        Edge(const size_t id=0, const size_t from=0, const size_t to=0, const Eattr &attr=Eattr()): from(from), to(to), attr(attr), id(id) {}
        bool operator==(const Edge &e) { return e.id == id; }
        
        struct hash {
            size_t operator()(const Edge &e) const {
                return e.id;
            }
        };

        friend std::ostream &operator<<(std::ostream &os, const Edge e) {
            os << e.attr;
            return os;
        }   

    private:
        size_t id;
    };

private:
    bool _is_valid(const size_t id) const;
    ArrayList<Vertex> _data;
    size_t _vertex_count;
    size_t _edge_count;
};

template <typename Vattr, typename Eattr>
Graph<Vattr, Eattr>::Graph(): _edge_count(0) { }

template <typename Vattr, typename Eattr>
size_t Graph<Vattr, Eattr>::set(const Vattr &attr) {
    size_t id = _vertex_count++;
    _data.push_back(Vertex(id, attr));
    return id;
}

template <typename Vattr, typename Eattr>
void Graph<Vattr, Eattr>::link(const size_t from, const size_t to, const Eattr &attr) {
    if(!_is_valid(from) || !_is_valid(to))
        throw "Unable to link!";
    _data[from].edges.push_back(Edge(_edge_count++, from, to, attr));
}

template <typename Vattr, typename Eattr>
const Graph<Vattr, Eattr>::Vertex &Graph<Vattr, Eattr>::get(const size_t id) const {
    if(!_is_valid(id))
        throw "Unable to find vertex!";
    return _data[id];
}

template <typename Vattr, typename Eattr>
void Graph<Vattr, Eattr>::remove(const size_t id) {
    size_t pos = _data.find(id);
    if(pos == _data.size())
        throw "Unable to find vertex!";
    else
        _data.erase(pos);
}

template <typename Vattr, typename Eattr>
void Graph<Vattr, Eattr>::unlink(const size_t from, const size_t to) {
    size_t pos = _data[from].find(to);
    if(pos == _data.size())
        throw "Unable to find vertex!";
    else
        _data[from].erase(pos);
}

template <typename Vattr, typename Eattr>
const ArrayList<typename Graph<Vattr, Eattr>::Vertex> &Graph<Vattr, Eattr>::vertexes() const {
    return _data;
}

template <typename Vattr, typename Eattr>
const ArrayList<std::reference_wrapper<typename Graph<Vattr, Eattr>::Edge>> &Graph<Vattr, Eattr>::edges() const {
    ArrayList<std::reference_wrapper<typename Graph<Vattr, Eattr>::Edge>> t;
    for(int i = 0 ; i < _data.size() ; i++) {
        // should be farely slow!
        for(int j = 0 ; j < _data.edges.size() ; j++) {
            t.push_back(std::ref(_data[i].edges[j]));
        }
    }
    return t;
}

template <typename Vattr, typename Eattr>
void Graph<Vattr, Eattr>::clear() {
    _data.clear();
}

template <typename Vattr, typename Eattr>
Graph<Vattr, Eattr>::~Graph() {
    _data.clear();
}

template <typename Vattr, typename Eattr>
bool Graph<Vattr, Eattr>::_is_valid(const size_t id) const {
    return id >= 0 && id < _data.size();
}

#endif